package jaro_distance

import (
	"bytes"
	"math"
)

/**
* Author: dinglin
* Date: 2022/2/18 3:13 下午
 */

/**
* Author: dinglin
* Date: 2022/2/17 2:15 下午
 */
const (
	maxP      float64 = 0.25
	maxPrefix int     = 4
)

// https://rosettacode.org/wiki/Jaro_similarity
func jaroDistance(a, b string) (simJ float64, l int) {
	if len(b) == 0 || len(a) == 0 {
		return 0, 0
	}
	runes1 := bytes.Runes([]byte(a))
	runes2 := bytes.Runes([]byte(b))
	nRunes1 := len(runes1)
	nRunes2 := len(runes2)
	if nRunes2 > nRunes1 {
		runes1, runes2 = runes2, runes1
		nRunes1, nRunes2 = nRunes2, nRunes1
	}
	//len(str1) >= len(str2)
	maxWindow := max((nRunes1>>1)-1, 0)
	runes1Matched := make([]bool, nRunes1)
	runes2Matched := make([]bool, nRunes2)
	matched := 0
	prefixCnt := 0
	transpositions := 0
	for i := range runes2 {
		for j := max(i-maxWindow, 0); j < min(i+maxWindow+1, nRunes1); j++ {
			if runes1Matched[j] || runes2[i] != runes1[j] { //已经匹配了或者当前不匹配
				continue
			}
			runes2Matched[i] = true
			runes1Matched[j] = true
			matched++
			break
		}

	}
	for i := range runes2 {
		if runes1[i] == runes2[i] {
			prefixCnt++
		}
	}
	j := 0
	for i := range runes2 {
		if !runes2Matched[i] {
			continue
		}
		for !runes1Matched[j] {
			j++
		}
		if runes2[i] != runes1[j] {
			transpositions++
		}
		j++
	}
	ret := float64(matched) / float64(nRunes1)
	ret += float64(matched) / float64(nRunes2)
	ret += 1 - (float64(transpositions/2) / float64(matched))
	return ret / 3, min(prefixCnt, maxPrefix)
}

func JaroDistance(a, b string) float64 {
	simJ, _ := jaroDistance(a, b)
	return simJ
}

//simW = simJ + l*p*(1-simJ)
func JaroWinklerDistanceWithP(p float64, a, b string) float64 {
	simJ, l := jaroDistance(a, b)
	if simJ == 0 {
		return 0
	}
	return simJ + float64(l)*math.Min(p, maxP)*(1.0-simJ)
}

func JaroWinklerDistance(a, b string) float64 {
	simJ, l := jaroDistance(a, b)
	if simJ == 0 {
		return 0
	}
	return simJ + float64(l)*0.1*(1.0-simJ)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
